/*
 * @lc app=leetcode.cn id=547 lang=cpp
 *
 * [547] 朋友圈
 */

// @lc code=start
class Solution {
public:
    int findCircleNum(vector<vector<int>>& M) {
        //并查集的模板题
        //并查集有两个优化方式，1是路径压缩，2是按秩合并，通常做1即可
        //STEP 0 : 每个节点的父亲初始化为自己
        //STEP 1 : 递归 满足合并条件
        //          p[find(a)] = find(b)
        //路径压缩：
        //void find(int x){
        //     if(pa[x] == pa) return x;
        //      else {
        //          pa[x] = find(pa[x]);
        //          return pa[x];
        //  }    
        //}

        const int N = M.size();
        for(int i = 0; i < N; i++)  pa.push_back(i);
        int ans = N;
        for(int i = 0; i < N; i++)
            for(int j = i + 1; j < N; j++){
                if(M[i][j] && find(i) != find(j)){
                    pa[find(i)] = find(j);
                    --ans;
                }
            }
        return ans;
    }
private:
    vector<int> pa;
    int find(int t){
        if(pa[t] == t) return t;
        else{
            pa[t] = find(pa[t]);
            return pa[t];
        }
    }
};
// @lc code=end

